package me.shan.data.structure;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;

import lombok.Data;
import me.shan.util.RandomUtils;

/**
 * 描述：双链表
 *
 * @author liuchuang
 * @date 2021/6/18 15:26
 */
@Data
public class DoubleLinkedList<T> {

    private DoubleNode<T> head;

    private int size = 0;

    public DoubleLinkedList() {

    }

    public DoubleLinkedList(T value) {
        this.head = new DoubleNode<>(value);
        this.size++;
    }

    public void add(T value) {
        if (this.size == 0) {
            this.head = new DoubleNode<>(value);
        } else {
            DoubleNode<T> pre = this.head;
            DoubleNode<T> current = pre.getNext();
            while (current != null) {
                pre = current;
                current = pre.getNext();
            }
            current = new DoubleNode<>(value);
            pre.setNext(current);
            current.setPre(pre);
        }
        this.size++;
    }

    private static <T> DoubleLinkedList<T> genDoubleLinkedListFromArrays(T[] arrays)
        throws Exception {
        if (arrays.length == 0) {
            throw new Exception("不支持空数组初始化链表");
        }
        DoubleLinkedList<T> doubleLinkedList = new DoubleLinkedList<>();
        for (T item : arrays) {
            doubleLinkedList.add(item);
        }
        return doubleLinkedList;
    }

    /**
     * 翻转链表
     */
    public void revers() {
        int minNeedReversSize = 2;
        if (size < minNeedReversSize) {
            return;
        }
        DoubleNode<T> pre = null;
        DoubleNode<T> node = head;
        DoubleNode<T> next;
        while (node != null) {
            next = node.getNext();
            node.setNext(pre);
            node.setPre(next);
            pre = node;
            node = next;
        }
        this.head = pre;
    }

    /**
     * 删除节点
     *
     * @param value 值
     */
    public void delete(T value) {
        if (head == null) {
            return;
        }
        while (head != null && Objects.equals(head.getValue(), value)) {
            head = head.getNext();
            this.size--;
        }
        if (head == null) {
            return;
        }
        // 删除首节点的pre指针
        head.setPre(null);
        DoubleNode<T> current = head;
        while (current != null) {
            if (Objects.equals(current.getValue(), value)) {
                this.size--;
                current.getPre().setNext(current.getNext());
                if (current.getNext() != null) {
                    current.getNext().setPre(current.getPre());
                }
            }
            current = current.getNext();
        }
    }

    public List<T> getList() {
        List<T> list = new ArrayList<>(size);
        DoubleNode<T> node = head;
        while (node != null) {
            list.add(node.getValue());
            node = node.getNext();
        }
        return list;
    }

    public static DoubleLinkedList<Integer> genRandomDoubleLinkList(int maxLen, int maxValue) {
        DoubleLinkedList<Integer> doubleLinkedList = new DoubleLinkedList<>();
        int length = RandomUtils.getRandomLen(maxLen);
        int count = 0;
        while (count < length) {
            doubleLinkedList.add(RandomUtils.getRandomValue(maxValue));
            count++;
        }
        return doubleLinkedList;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("正序遍历 DoubleLinkedList{size=");
        stringBuilder.append(this.size);
        if (this.size == 0) {
            stringBuilder.append(", doubleNode={ null }}");
        } else {
            stringBuilder.append(", doubleNode={ null <--- ");
            DoubleNode<T> node = this.head;
            DoubleNode<T> pre = null;
            while (node != null) {
                stringBuilder.append(node.getValue());
                pre = node;
                node = node.getNext();
                if (node != null) {
                    stringBuilder.append(" <===> ");
                }
            }
            stringBuilder.append(" ---> null }}");

            stringBuilder.append("\n");
            stringBuilder.append("逆序遍历 DoubleLinkedList{size=");
            stringBuilder.append(this.size);
            stringBuilder.append(", doubleNode={ null <--- ");
            while (pre != null) {
                stringBuilder.append(pre.getValue());
                pre = pre.getPre();
                if (pre != null) {
                    stringBuilder.append(" <===> ");
                }
            }
            stringBuilder.append(" ---> null }}");
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) throws Exception {
        int maxLen = 1000;
        int maxValue = 100000;
        int times = 1000;
        System.out.println("翻转测试开始");
        long startTime = System.currentTimeMillis();
        while (times > 0) {
            DoubleLinkedList<Integer> doubleLinkedList = genRandomDoubleLinkList(maxLen, maxValue);
            List<Integer> list = doubleLinkedList.getList();
            doubleLinkedList.revers();
            if (checkFail(doubleLinkedList, list)) {
                System.out.println("有bug，赶紧改吧骚年");
            }
            times--;
        }
        long endTime = System.currentTimeMillis();
        System.out.println("测试结束，共耗时：" + (endTime - startTime) / 1000 + "秒");

        System.out.println("删除测试开始");
        times = 10000;
        while (times > 0) {
            DoubleLinkedList<Integer> doubleLinkedList = genRandomDoubleLinkList(maxLen, maxValue);
            List<Integer> list = doubleLinkedList.getList();
            List<Integer> temp = doubleLinkedList.getList();
            // 随机删除一个数
            int index = (int) (Math.random() * list.size());
            int num = list.get(index);
            doubleLinkedList.delete(num);
            list.removeAll(Collections.singleton(num));
            if (checkDeleteFail(doubleLinkedList, list)) {
                System.out.println("删除有bug，赶紧改吧骚年，数据样本：" + temp + "，删除的数：" + num);
            }
            times--;
        }
        deleteTest();
        System.out.println("删除测试结束");
    }

    private static void deleteTest() throws Exception {
        Integer[] array = {645, 140, 592, 680, 200, -634, 523, -99, -178, -531, -720, 213, -355, 128, -296, 26, 264, -601, -295, -237, -532, 704, -266, 167, 264, -404, -107, -584, -699, -128, -298, -362, -216, 641, 676, -575, -25, -66, -229, -56, 367, 459, -188, 222, 626, 72, -19, 219, 407, -404, 470, 275, 120, 538, 390, 508, 753, 336, 32, -204, -164, 700, 565, -110, 656, -338, 271, 290, -214, -80, 418, 451, 65, 62, -155, -62, 77, 285, 377, 94, 263, 176, 144, -157, -272, 176, -90, 199, -146, 294, 492, 100, -183, 686, 387, 124, 79, -314, -329, 725, -20, 874, 289, 545, -510, -212, -189, -584, 250, -131, 761, 647, -38, -775, -393, 170, 247, -180, 502, 161, 49, -325, -114, -274, -305, 678, 11, 229, 682, 586, -477, -125, 307, -164, 163, 133, 216, -271, 693, 592, -11, 606, 141, -147, 817, -404, -537, 28, -592, 534, -299, 476, 188, 644, -253, -668, -109, 573, -206, 446, -349, 385, -418, 327, -330, 86, -484, 661, -437, 308, -239, 30, -524, -299, 410, 405, 75, -335, 804, 7, -524, 2, 116, 139, -755, 75, -720, -424, 540, 77, 359, 116, -517, -1, 462, -139, -123, 896, -724, -139, -655, 37, 337, 675, -11, -460, 102, -523, 672, 79, -49, 265, -11, -731, 181, -194, 69, 300, 103, -121, 247, -557, 335, -573, 736, -6, 379, 200, 390, 273, 573, -499, -371, 256, -468, -396, 646, -567, 138, 461, -26, -493, 208, 277, -481, -505, -94, -455, 130, -141, 10, -840, -170, 226, 122, 165, 779, 328, -90, -241, 75, 719, 486, 135, -523, 892, 4, -228, 152, 372, -422, -272, -462, 387, -390, -416, -586, -293, -372, 586, 269, 250, -288, -402, 74, 37, -372, -530, -462, -892, -261, -604, -50, -28, -204, -144, -301, -796, 705, -236, -439, -228, 369, 370, -147, -321, 676, -449, 552, 546, -243, 70, 452, -318, -413, -625, -518, 287, 26, 578, 251, 334, -595, 163, -61, 759, -268, 42, -398, 536, 632, -451, 10, 225, 97, -47, 90, -384, 155, 106, 87, 14, -466, 799, -484, -180, 437, 430, 20, -61, 503, 573, -784, 655, 55, -946, -381, 553, 727, 107, -257, 62, -426, -778, 484, 254, -263, -731, 861, 446, -222, -505, 205, 234, -231, -11, 920, 539, 231, 205, -126, -742, 9, 139, 541, 115, 192, -243, -32, 308, -837, 253, 671, 545, -133, -237, -443, 57, 399, 83, -41, 196, 9, 32, -129, 188, -396, 14, -502, -329, -143, -599, -804, -437, 4, -688, -105, -98, 428, -599, 123, 225, 125, 218, -312, 76, 141, 777, 143, 258, 85, -115, 113, 406, -208, -148, -425, 477, 249, 163, 205, -243, -128, -279, 849, -26, 216, 223, 254, 103, 229, 308, 121, -509, 142, 26, 593, 831, 69, 255, -751, -341, -567, -362, -263, -106, -695, 653, 92, 65, -251, 386, -132, -201, 255, 625, -831, 162, 382, -146, 656, -549, 670, -253, -345, 33, -47, -260, 429, -176, 120, 314, -279, -7, -531, -470, -320, -506, -291, 455, -782, 30, -283, 41, -61, 4, -847, 77, -295, 103, 5, -214, -49, 71, 184, -327, -179, 270, -759, 207, 238, -354, 306, -46, 0, -337, -642, -277, -21, 815, -108, 343, -465, 316, 96, -347, 238, -462, -369, -700, -27, -175, 101, -50, 545, 237, 307, -512, -133, -142, -609, -190, -186, -775, -65, -196, -134, 506, 155, 103, -400, -15, 231, 223, 150, 481, -97, -346, -288, 278, 425, -484, 204, 156, -53, 373, 159, -879, 436, -212, -52, -556, 240, 222, 443, 573, -640, -128, -810, 532, -451, 29, 200, -601, 327, -434, -551, 448, -19, 142, 180, 558, 692, 710, -901, -524, -164, -65, 568, -465, 572, 109, -131, -586, -174, 151, 659, 532, -275, 300, -315, 681, 622, 85, -133, 481, -231, 161, -152, 255, 748, 623, 80, -82, -245, 366, -430, 470, 821, 114, -638, -306, 76, 682, -156, 647, 136, 90, -3, -468, -278, 109, 655, -432, -411, -169, -123, 420, -125, -132, 540, -196, -52, 767, 227, -140, -143, -772, -499, -126, 471, 736, 690, -45, 412, 179, -763, -745, 859, 71, -263, -667, 334, -52, -255, 237, 557, 547, -563, 928, -553, 361, 251, -386, 403, 153, -445, 595, -86, 42, 487, -773, -382, 724, 9, -430, -96, 466, -685, -652, 133, 412, -342, -219, -406, -150, 692, -92, -731, -8, -555, -11, -483, -118, -20, -436, -242, 24, -126, -211, 257, -691, -407, -384, 106, -143, -162, 440, -519, -649, 3, 770, 298, -534, 784, -447, 322, -26, 77, -271, 858, 144, 229, 606, 100, -5, -242, -347, 233, 34, -385, -682, -611, 40, 98, -562, -459, -493, -494, 861, -568, 337, 626, -145, -354, -625, 140, -88, -111, 365, 65, 525, -405, -40, -696, 553, -58, 329, 395, 743, 377, -1, -422, 18, -268, -503, 248, -865, 44, 397, -99, 273, 149, -632, -337, 180, 167, -185, 494, -547, -43, 694, -830, 548, -363, 117, 120, 129, -728, 330, -771, 307, -189, -354, -308, -568, -623, -51, 8, -45, 0, 348, 223, 15, -116, 581, -500, 309, -697, -248, 117, -147, 232, 12, -7, 229, -217, 769, -188, -103, 551, 13, -121, 190, -15, 362, -246, -438, -165, 419, 805, 698, -194, 34, -271, 70, 492, 57, -827, -453, 696, 186, 525, -372, -782, -494, -24, -78, 215, 294, -50, -553, 221, -289, -12, -655, 922, -52, 186, -383, -214, -562, 285, 464, -378, -277, 489, -182, 191, 567, 125, -312, -59, -96, 230, -129, -40, 235, 156, -337, -742, 41, -710, 137, -545, 826, -18, -406, -27, 367, -219, -231, -172, -210, 59, -592, -879, 36, 131, -214, 301, -672, -50, -233, 330, 230};
        int num = 221;
        DoubleLinkedList<Integer> doubleLinkedList = DoubleLinkedList.genDoubleLinkedListFromArrays(array);
        List<Integer> list = doubleLinkedList.getList();
        doubleLinkedList.delete(num);
        list.removeAll(Collections.singleton(num));
        System.out.println(checkDeleteFail(doubleLinkedList, list));
    }

    private static boolean checkFail(DoubleLinkedList<Integer> doubleLinkedList,
                                     List<Integer> list) {
        if (doubleLinkedList.size != list.size()) {
            return true;
        }
        int index = list.size() - 1;
        DoubleNode<Integer> doubleNode = doubleLinkedList.head;
        while (index >= 0) {
            if (!doubleNode.getValue().equals(list.get(index))) {
                return true;
            }
            doubleNode = doubleNode.getNext();
            index--;
        }
        return false;
    }

    private static boolean checkDeleteFail(DoubleLinkedList<Integer> doubleLinkedList, List<Integer> list) {
        // 从头到尾，从尾到头结果都一致，就认为结果是对的
        DoubleNode<Integer> doubleNode = doubleLinkedList.head;
        if (doubleNode == null && list.size() == 0) {
            return false;
        }
        DoubleNode<Integer> tail = null;
        for (Integer num : list) {
            if (!Objects.equals(num, doubleNode.getValue())) {
                return true;
            }
            if (doubleNode.getNext() == null) {
                tail = doubleNode;
            }
            doubleNode = doubleNode.getNext();
        }
        if (doubleNode != null) {
            return true;
        }
        // 逆序遍历
        for (int i = list.size() - 1; i >= 0; i--) {
            Integer num = list.get(i);
            if (!Objects.equals(num, tail.getValue())) {
                return true;
            }
            tail = tail.getPre();
        }
        return tail != null;
    }
}

@Data
class DoubleNode<T> {

    /**
     * 值
     */
    private T value;

    private DoubleNode<T> pre;

    private DoubleNode<T> next;

    public DoubleNode(T value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return String.format("%s <-- %s --> %s", pre == null ? null : pre.value, value, next == null ? null : next.value);
    }

}
